After VLSI circuits are fabricated on a chip it is necessary to test the circuit for defects or faults. An initial step in the test process is the determination of a test vector which when converted to electrical signals is applied to the inputs of the circuit in order to cause predetermined signals to be manifest as circuit outputs. By monitoring these output signals it is possible to locate defects and/or faults in the VLSI circuit.
Test generation is a process of generating input stimuli, known as test vectors, to a VLSI circuit in order to test for possible defects in the circuit chip by producing observable faulty responses at the chip outputs.
Since the test generation problem is NP-complete, currently used methods are, of necessity, based on heuristic search methods. The majority of these methods are based on combinatorial search techniques that utilize circuit-specific knowledge to systematically explore the search space for a test vector. In each of these methods, signals in the circuit assume only discrete binary values.
An article by S. T. Chakradhar, V. D. Agrawal and M. L. Bushnell entitled "On Test Generation Using Neural Computers" in the International Journal of Computer Aided VLSI Design, Vol. 3, March 1991, pages 241-257 describes a test generation technique based on analog neural networks which generates test vectors by allowing signals to assume any real value between 0 and 1. However, since large scale neural networks arc not presently available, only small circuit can be processed by this technique.
A simulation based cost function approach to using non-binary values for signals has been proposed in the book by K. T. Cheng and V. D. Agrawal entitled "Unified Methods for VLSI Simulation and Test Generation" by Kluwer Academic Publishers, 1989 and in an article by K. Hatayama et al entitled "Sequential Test Generation Based on Real-Valued Logic Simulation" in the Proceedings of the International Test Conference 1992, pp. 41-48.